package 单周赛.history;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *
 */
public class 第296场单周赛 {

    public static void main(String[] args) {

        int[] nums = {1, 3, 5, 2, 4, 8, 2, 2};
        System.out.println(minMaxGame(nums));

        int[] nums2 = {3, 6, 1, 2, 5};
        System.out.println(partitionArray(nums2, 2));

        int[] nums3 = {1, 2};
        int[][] op = {{1, 3}, {2, 1}, {3, 2}};
        System.out.println(Arrays.toString(arrayChange(nums3, op)));

    }

    /**
     * 其长度是 2 的幂，不用考虑奇数
     * 递归模拟
     *
     * @param nums
     * @return
     */
    public static int minMaxGame(int[] nums) {
        if (nums.length == 1) return nums[0];
        int[] nextNums = new int[nums.length / 2];

        boolean isMin = true;
        for (int i = 0, j = 0; i < nums.length; i += 2, j++) {
            if (isMin) {
                nextNums[j] = Math.min(nums[i], nums[i + 1]);
                isMin = false;
            } else {
                nextNums[j] = Math.max(nums[i], nums[i + 1]);
                isMin = true;
            }
        }
        return minMaxGame(nextNums);
    }

    /**
     * 不用返回具体的子序列
     * 排序+模拟
     *
     * @param nums
     * @param k
     * @return
     */
    public static int partitionArray(int[] nums, int k) {
        int partCount = 0;
        Arrays.sort(nums);
        int curMin = nums[0];
        int index = 0;
        while (index < nums.length) {
            while (index < nums.length && nums[index] - curMin <= k) index++;
            if (index != nums.length) curMin = nums[index];
            partCount++;
        }
        return partCount;
    }

    /**
     * 保证在第 i 个操作中：
     * operations[i][0] 在 nums 中存在。
     * operations[i][1] 在 nums 中不存在。
     * <p>
     * 题目保证 nums 起始和过程中 某个数字只出现一次
     * 先将nums[i] 和 索引 i ，存入哈希表中，实时更新
     *
     * @param nums
     * @param operations
     * @return
     */
    public static int[] arrayChange(int[] nums, int[][] operations) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int[] operation : operations) {
            Integer index = map.get(operation[0]);
            nums[index] = operation[1];
            map.put(nums[index], index);
        }
        return nums;
    }

}
